package com.frx.leetoffer.binarytree;

import java.util.*;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/11/5
 * @Time: 9:41
 */
public class OrderBinary {
    public static void main(String[] args){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3,node1,node2);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6,node4,node5);
        TreeNode node7 = new TreeNode(7,node3,node6);
        preOrder(node7);
        System.out.println();
        pre(node7);
        System.out.println();
        levelOrder(node7);
        System.out.println();
        System.out.println(zigOrder(node7));
    }
    public static List<List<Integer>> zigOrder(TreeNode root){
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        // 一个双向队列
        Deque<TreeNode> nodeDeque = new ArrayDeque<>();
        nodeDeque.addFirst(root);
        int L = 1;
        while (!nodeDeque.isEmpty()){
            int size = nodeDeque.size();
            list.add(new ArrayList<>());
            // 奇数层的节点
            for (int i=0;L%2 > 0 && i<size;i++){
                TreeNode node = nodeDeque.pollFirst();
                list.get(list.size()-1).add(node.val);
                // 下一层的非空左节点和右节点在尾部入栈
                if (node.left!=null){
                    nodeDeque.addLast(node.left);
                }
                if (node.right!=null){
                    nodeDeque.addLast(node.right);
                }
            }
            for (int i=0;L%2==0&&i<size;i++){
                TreeNode node = nodeDeque.pollLast();
                list.get(list.size()-1).add(node.val);
                if (node.right != null){
                    nodeDeque.addFirst(node.right);
                }
                if (node.left != null){
                    nodeDeque.addFirst(node.left);
                }
            }
            L++;
        }


        return list;
    }


    public static void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.remove();
            System.out.print(cur.val + " ");
            if (cur.left != null){
                queue.add(cur.left);
            }
            if (cur.right != null){
                queue.add(cur.right);
            }
        }
    }


    public static void pre(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        pre(root.left);
        pre(root.right);
    }

    public static void preOrder(TreeNode root){
        if (root == null){
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            System.out.print(cur.val + " ");
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left != null){
                stack.push(cur.left);
            }

        }

    }
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }

    public TreeNode(int val,TreeNode left,TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }

}
